import java.util.Arrays;

public class Test {

//冒泡排序
    public static void paoSort(int[] a){
        for(int i=0;i<a.length;i++){
            for(int j=0;j<a.length-i-1;j++){
                if(a[j]>a[j+1]){
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }
    }

    //快排
    public static void quickSort(int[] a,int left,int right){
        if(left<right){
            int mid = getPivot(a,left,right);
            quickSort(a,left,mid-1);
            quickSort(a,mid+1,right);
        }
    }
    public static  int getPivot(int[]a,int left,int right){
        int i = left;
        int j = right;
        int temp = a[i];
        while(i<j){
            //先从右边找第一个小于temp的
            while(j>i&&a[j]>=temp)
                j--;
            a[i] = a[j];
            //再从左往右找第一个大于temp的
            while (i<j&&a[i]<=temp)
                i++;
            a[j] = a[i];
        }
        a[i] = temp;
        return i;
    }

    //堆排序
    public static void headSort(int[] a){
        //首先先构建大顶堆
        int n= a.length;
        for(int i=n/2-1;i>=0;i--){
            downAdjust(a,i,n-1);
        }
        //然后把第一个元素移到末尾
        for(int i=n-1;i>=1;i--){
            int temp = a[i];
            a[i] = a[0];
            a[0] = temp;
            //此时顺序变了，不符合大顶堆，再次调整构建大顶堆
            downAdjust(a,0,i-1);
        }

    }

    public static void downAdjust(int[] a,int parent,int n){
        //先用一个临时变量记录当前要下沉的数
        int temp = a[parent];
        int child = parent*2+1;//用于记录孩子下标,当前为左孩子
        while(child<=n){
            if(child+1<=n&&a[child+1]>a[child]){
                child++;
            }
            if(a[child]<=temp) break;
            //接下来进行下沉
            a[parent] = a[child];
            parent = child;
            child = child*2+1;
        }
        a[parent] = temp;
    }

    //归并排序
    public static void mergeSort(int[] a,int left,int right){
        if(left<right){
            int mid = (left+right)/2;
            mergeSort(a,left,mid);
            mergeSort(a,mid+1,right);
            merge(a,left,mid,right);
        }
    }
    public static void merge(int[] a,int left,int mid,int right){
        int[] arr = new int[right-left+1];
        int i=left;
        int j=mid+1;
        int k=0;
        while (i<=mid&&j<=right){
            if(a[i]<=a[j]){
                arr[k++] = a[i++];
            }else{
                arr[k++] = a[j++];
            }
        }
        while (i<=mid)
            arr[k++] = a[i++];
        while (j<=right)
            arr[k++] = a[j++];
        for(i =0;i<k;i++){
            a[left++] = arr[i];
        }

    }

    public static void main(String[] args){
       int[] a = {1,41,2,4,5,1,8,74,4};
       //quickSort(a,0,a.length-1);
       mergeSort(a,0,a.length-1);
      for(int i : a)
          System.out.print(i+" ");
    }
}
